package com.example.algorithm.backtrcaking.backrewrite;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author : zhy
 * @since : 2022/8/23
 * 回文数
 */
public class HuiWenNum {

    List<List<String>> list=new ArrayList<>();
    List<String> deque=new ArrayList<>();
    public List<List<String>> partition(String s) {
        int len= s.length();
        backTrecking(s,0,len);
        return list;
    }

    private void backTrecking(String s,int startIndex, int endIndex) {

        if(startIndex>=endIndex)
        {
            list.add(new ArrayList<>(deque));
            return;
        }

        for(int i=startIndex;i<endIndex;i++)
        {
            if(!isHuiWen(s,startIndex,i))
            {
                continue;
            }
            deque.add(s.substring(startIndex,i+1));
            backTrecking(s,i+1,endIndex);
            deque.remove(deque.size()-1);
        }
    }

    private boolean isHuiWen(String s, int startIndex, int endIndex) {
        while(startIndex<=endIndex)
        {
            if(s.charAt(startIndex)!=s.charAt(endIndex))
            {
                return false;
            }
            startIndex++;
            endIndex--;
        }
        return true;
    }


    public static void main(String[] args) {
        HuiWenNum huiWenNum = new HuiWenNum();
        List<List<String>> aab = huiWenNum.partition("abcd");
        aab.stream().forEach(System.out::println);
    }
}
